// https://leetcode.cn/problems/lfu-cache/description/

// 算法思路总结：
// 1. 使用双哈希表+双向链表实现LFU缓存
// 2. 一个哈希表按频率存储节点链表，另一个记录键到迭代器的映射
// 3. 维护最小频率，淘汰时移除最小频率的LRU节点
// 4. 访问节点时提升频率并更新位置
// 5. 时间复杂度：O(1)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <list>

class LFUCache
{
private:
    struct Node
    {
        int key;
        int value;
        Node(int k, int v) : key(k), value(v) {}
    };

    typedef list<Node>::iterator NodeIter;
    typedef unordered_map<int, list<Node>>::iterator FreqIter;

    int _capacity;
    int _minFreq;

    unordered_map<int, pair<NodeIter, FreqIter>> _keyMap;
    unordered_map<int, list<Node>> _freqMap;

public:
    LFUCache(int capacity)
        : _capacity(capacity),
          _minFreq(0)
    {
    }

    int get(int key)
    {
        auto ret = _keyMap.find(key);
        if (ret != _keyMap.end())
        {
            FreqIter freqIt = ret->second.second;
            NodeIter nodeIt = ret->second.first;

            int value = nodeIt->value;
            int oldFreq = freqIt->first;
            int newFreq = oldFreq + 1;

            _freqMap[newFreq].splice(_freqMap[newFreq].begin(),
                                     freqIt->second, nodeIt);

            if (freqIt->second.empty())
            {
                _freqMap.erase(freqIt);
                if (_minFreq == oldFreq)
                {
                    _minFreq = newFreq;
                }
            }

            _keyMap[key].second = _freqMap.find(newFreq);

            return value;
        }
        else
        {
            return -1;
        }
    }

    void put(int key, int value)
    {
        if (_capacity == 0)
            return;

        auto ret = _keyMap.find(key);
        if (ret == _keyMap.end())
        {
            if (_capacity == _keyMap.size())
            {
                auto &minFreqList = _freqMap[_minFreq];
                Node lruNode = minFreqList.back();

                _keyMap.erase(lruNode.key);
                minFreqList.pop_back();

                if (minFreqList.empty())
                {
                    _freqMap.erase(_minFreq);
                }
            }

            _freqMap[1].emplace_front(key, value);
            _keyMap[key] = make_pair(_freqMap[1].begin(), _freqMap.find(1));
            _minFreq = 1;
        }
        else
        {
            FreqIter freqIt = ret->second.second;
            NodeIter nodeIt = ret->second.first;

            int oldFreq = freqIt->first;
            int newFreq = oldFreq + 1;

            nodeIt->value = value;

            _freqMap[newFreq].splice(_freqMap[newFreq].begin(),
                                     freqIt->second, nodeIt);

            if (freqIt->second.empty())
            {
                _freqMap.erase(freqIt);
                if (_minFreq == oldFreq)
                {
                    _minFreq = newFreq;
                }
            }

            _keyMap[key].second = _freqMap.find(newFreq);
        }
    }
};

int main()
{
    LFUCache *lfu = new LFUCache(2);
    lfu->put(1, 1);              // cache=[1,_], cnt(1)=1
    lfu->put(2, 2);              // cache=[2,1], cnt(2)=1, cnt(1)=1
    cout << lfu->get(1) << endl; // 返回 1
                                 // cache=[1,2], cnt(2)=1, cnt(1)=2
    lfu->put(3, 3);              // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                                 // cache=[3,1], cnt(3)=1, cnt(1)=2
    cout << lfu->get(2) << endl; // 返回 -1（未找到）
    cout << lfu->get(3) << endl; // 返回 3
                                 // cache=[3,1], cnt(3)=2, cnt(1)=2
    lfu->put(4, 4);              // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                                 // cache=[4,3], cnt(4)=1, cnt(3)=2
    cout << lfu->get(1) << endl; // 返回 -1（未找到）
    cout << lfu->get(3) << endl; // 返回 3
                                 // cache=[3,4], cnt(4)=1, cnt(3)=3
    cout << lfu->get(4) << endl; // 返回 4
                                 // cache=[3,4], cnt(4)=2, cnt(3)=3

    return 0;
}